// re.cpp
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include "util/standard.hpp"
#include <cstring>
#include "util/re.hpp"
#include "util/mem.hpp"
#include "util/token.hpp"
#include "util/packrat.hpp"

namespace Ripe {

// Types of tokens and AST nodes used when compiling a regular expression.
#define RE_DOT 1       // Token '.'
#define RE_LETTER 2    // A letter.
#define RE_BOX 3       // Token [...] (match many characters)
#define RE_STAR 10     // Token '*'
#define RE_QUESTION 11 // Token '?'
#define RE_PLUS 12     // Token '+'
#define RE_PIPE 13     // Token '|'
#define RE_CONCAT 14   // No token, but used in AST.
#define RE_LPAREN 21   // Token '('
#define RE_RPAREN 22   // Token ')'

// Subexpression of a regular expression.
struct RESubExpression {
  NFANode* input;
  NFANode* output; // Linked list of output nodes.
};

// An element of a [...] part of a regular expression. May be a match
// of a single character, or a match of a range of characters a-b.
#define RE_SINGLE 1
#define RE_RANGE  2
struct REBoxElement{
  uint8_t type;      // May be RE_SINGLE or RE_RANGE.
  UniChar char1;
  UniChar char2;     // Used if type = RE_RANGE.
};

// Static functions:

// sub-expression := sub-expression | sub-expression
static RESubExpression re_alter(RESubExpression first,
                                RESubExpression second);

// Construct a RESubExpression from a REBoxElement list.
static RESubExpression re_box(Vector<REBoxElement>* v, bool negative);

// sub-expression := sub-expression sub-expression
static RESubExpression re_concat(RESubExpression first,
                                 RESubExpression second);

// Construct a sub-expression matching any character (dot).
static RESubExpression re_dot();

// Construct a sub-expression matching a single character.
static RESubExpression re_letter(UniChar letter);

// sub-expression := sub-expression +
static RESubExpression re_plus(RESubExpression expr);

// sub-expression := sub-expression ?
static RESubExpression re_question(RESubExpression expr);

// Route a linked list of outputs to a given node.
static void re_route(NFANode* output, NFANode* target);

// sub-expression := sub-expression *
static RESubExpression re_star(RESubExpression expr);

// A subclass of Token: used for tokenizing the input regular expression.
class REToken : public Token {
  public:
    UniChar c;  // Used for a RE_LETTER
    Vector<REBoxElement>* v; // Used for RE_BOX;
    bool negative; // Used with RE_BOX - indication that RE contains a ^
};

// AST node for a regular expression. If type = RE_DOT, no other fields
// are used. If type = RE_LETTER, extra is a uni_char*. If type = RE_STAR,
// RE_QUESTION or RE_PLUS, node1 is used. If type = RE_PIPE or RE_CONCAT, both
// node1 and node2 are used.
class RENode {
  public:
    RENode(uint8_t type, REToken* extra, RENode* node1, RENode* node2);

    uint8_t type;
    REToken* extra;
    RENode* node1;
    RENode* node2;
};

// Assemble a regular expression NFA out of RENode tree
static RESubExpression re_assemble(RENode* node);

// Nonterminals used in parsing a regular expression, and associated matchers.
#define RE_EXPR   0    // expr :=  expr ('+'|'?'|'*')  precedence: 3
                       //        | expr expr           precedence: 2
                       //        | expr '|' expr       precedence: 1
static Semantic match_expr(Parsing* p, int precedence);

Semantic match_expr(Parsing* p, int precedence)
{
  Semantic e1, e2;
  State s;
  Token* token;

  // Save the state at first.
  s = p->save();

  // precedence: 3
  // expr ::= expr (* | +)
  if (precedence <= 3)
    if ((e1 = p->match(RE_EXPR, 3))){
      if (p->consume(RE_STAR, &token)){
        return rnew RENode(RE_STAR, NULL, (RENode*) e1, NULL);
      }

      if (p->consume(RE_PLUS, &token)){
        return rnew RENode(RE_PLUS, NULL, (RENode*) e1, NULL);
      }

      if (p->consume(RE_QUESTION, &token)){
        return rnew RENode(RE_QUESTION, NULL, (RENode*) e1, NULL);
      }

    }

  p->restore(s);
  // precedence: 2
  // expr ::= expr expr
  if (precedence <= 2)
    if ((e1 = p->match(RE_EXPR, 2)))
      if ((e2 = p->match(RE_EXPR, 2))){
        return rnew RENode(RE_CONCAT, NULL, (RENode*) e1, (RENode*) e2);
      }

  p->restore(s);
  // precedence: 1
  // expr ::= expr | expr
  if (precedence <= 1)
    if ((e1 = p->match(RE_EXPR, 1)))
      if (p->consume(RE_PIPE, &token))
        if ((e2 = p->match(RE_EXPR, 1))){
          return rnew RENode(RE_PIPE, NULL, (RENode*) e1, (RENode*) e2);
        }

  // Match empty parentheses
  p->restore(s);
  if (p->consume(RE_LPAREN, &token))
    if (p->consume(RE_RPAREN, &token))
      // Empty parens. Consume and keep going.
      s = p->save();

  p->restore(s);
  // expr ::= '(' expr ')'
  if (p->consume(RE_LPAREN, &token))
    if ((e1 = p->match(RE_EXPR, 0)))
      if (p->consume(RE_RPAREN, &token))
        return e1;

  // Handle tokens.
  p->restore(s);
  if (p->read(&token)){
    // There is more input.
    switch(token->type){
      case RE_LETTER:
      case RE_DOT:
      case RE_BOX:
        return rnew RENode(token->type, (REToken*) token, NULL, NULL);
      default:
        return NULL;
    }
  }
  return NULL;
}

RENode::RENode(uint8_t t, REToken* e, RENode* n1, RENode* n2)
{
  type = t;
  extra = e;
  node1 = n1;
  node2 = n2;
}

RESubExpression re_alter(RESubExpression a, RESubExpression b)
{
  // Construct a split node
  NFASplitNode* split_node = rnew NFASplitNode;
  split_node->children.append(a.input);
  split_node->children.append(b.input);

  // Now we want to connect the outputs of a and b into result.output:
  // Find end of first linked list.
  NFANode* node = a.output;
  while (node->extra != NULL) node = node->extra;
  // Append the outputs of second subexpression
  node->extra = b.output;

  RESubExpression result;
  result.input = split_node;
  result.output = a.output;
  return result;
}

RESubExpression re_box(Vector<REBoxElement>* v, bool negative)
{
  NFACharNode* node = rnew NFACharNode;
  for (unsigned int i = 0; i < v->size; i++){
    REBoxElement e = (*v)[i];
    NFAMatchingClass mc = {ClassSingle, e.char1, e.char2};
    if (e.type == RE_RANGE) {
      mc.type = ClassRange;
    }
    node->match_classes.append(mc);
  }
  node->negative = negative;

  RESubExpression result;
  result.input = node;
  result.output = node;
  return result;
}

NFANode* re_compile(const char* expression, int term_id)
{
  // A note on the compilation of a RE:
  //
  //   1. The expression is tokenized.
  //   2. The expression is parsed using a packrat parser. An AST is
  //      constructed from the parsing.
  //   3. Using the AST, RESubExpressions are mangled together to construct
  //      the NFA.

  // Tokenize the expression.
  const char* cur = expression;
  const char* end = cur + strlen(expression);
  Vector<REToken*>* token_list = rnew Vector<REToken*>;

  try {
    while (cur != end){
      UniChar letter;
      letter = read_uni_char(&cur, end);
      REToken* token = rnew REToken;
      Vector<REBoxElement>* v;
      bool negative;
      const char* temp; UniChar temp_letter;

      switch(letter){
        case '.':
          token->type = RE_DOT;
          break;
        case '+':
          token->type = RE_PLUS;
          break;
        case '?':
          token->type = RE_QUESTION;
          break;
        case '*':
          token->type = RE_STAR;
          break;
        case '|':
          token->type = RE_PIPE;
          break;
        case '(':
          token->type = RE_LPAREN;
          break;
        case ')':
          token->type = RE_RPAREN;
          break;
        case '[':
          // Now tokenize a "box"
          v = rnew Vector<REBoxElement>;
          temp = cur;
          temp_letter = read_uni_char(&temp, end);
          negative = (temp_letter == '^') ? true : false;
          if (negative) cur = temp; // Consume fist character

          // Read letters until you hit a ']'
          while(true) {
            REBoxElement box_elem;

            letter = read_uni_char(&cur, end);
            if (letter == ']') break;
            if (letter == '\\') letter = read_uni_char(&cur, end);

            // Check if the next letter is a '-'
            temp = cur;
            temp_letter = read_uni_char(&temp, end);
            if (temp_letter == '-'){
              // Read one more letter.
              temp_letter = read_uni_char(&temp, end);
              if (temp_letter == '\\') temp_letter = read_uni_char(&temp, end);

              box_elem.type = RE_RANGE;
              box_elem.char1 = letter;
              box_elem.char2 = temp_letter;
              cur = temp;
            } else {
              box_elem.type = RE_SINGLE;
              box_elem.char1 = letter;
            }
            v->append(box_elem);
          }
          // Don't allow [] or [^] in a RE
          if (v->size == 0) throw ErrorInvalidRE();

          token->type = RE_BOX;
          token->negative = negative;
          token->v = v;
          break;
        case '\\':
          // Match the following letter:
          letter = read_uni_char(&cur, end);
          // proceed to default.
        default:
          // Any letter.
          token->type = RE_LETTER;
          token->c = letter;
      }

      // Finally add the token
      token_list->append(token);
    }
  } catch (ErrorUTF8Limited e) {
    throw ErrorInvalidRE();
  }

  // Parse the expression.
  Parsing parsing;
  parsing.tokens = (Vector<Token*>*)token_list;
  parsing.grammar.set(RE_EXPR, match_expr);
  Semantic ast = parsing.parse(RE_EXPR);

  if (ast == NULL) throw ErrorInvalidRE();

  RESubExpression expr = re_assemble((RENode*) ast);

  // Add a terminating node to the expression
  NFATermNode* term_node = rnew NFATermNode();
  term_node->id = term_id;
  re_route(expr.output, term_node);
  return expr.input;
}

RESubExpression re_assemble(RENode* node)
{
  assert(node != NULL);
  switch(node->type){
    case RE_STAR:
      return re_star(re_assemble(node->node1));
    case RE_PLUS:
      return re_plus(re_assemble(node->node1));
    case RE_QUESTION:
      return re_question(re_assemble(node->node1));
    case RE_CONCAT:
      return re_concat(re_assemble(node->node1),
                       re_assemble(node->node2));
    case RE_PIPE:
      return re_alter(re_assemble(node->node1),
                      re_assemble(node->node2));
    case RE_LETTER:
      return re_letter(node->extra->c);
    case RE_DOT:
      return re_dot();
    case RE_BOX:
      return re_box(node->extra->v, node->extra->negative);
  }
  assert_never();
  return re_dot();
}

RESubExpression re_concat(RESubExpression a, RESubExpression b)
{
  /* Route the outputs of A into input of B */
  re_route(a.output, b.input);

  RESubExpression result;
  result.input = a.input;
  result.output = b.output;
  return result;
}

RESubExpression re_dot()
{
  NFACharNode* node = rnew NFACharNode;
  NFAMatchingClass mc = {ClassAny, 0, 0};
  node->match_classes.append(mc);

  RESubExpression result;
  result.input = node;
  result.output = node;
  return result;
}

RESubExpression re_letter(UniChar letter)
{
  NFACharNode* node = rnew NFACharNode;
  NFAMatchingClass mc = {ClassSingle, letter, 0};
  node->match_classes.append(mc);

  RESubExpression result;
  result.input = node;
  result.output = node;
  return result;
}

bool re_match(const char* s, NFANode* pattern, bool greedy, int* id, 
              int* length)
{
  const char* start = s;
  const char* end = s + strlen(s);

  NFAState state;
  pattern->activate(&state);

  // These are used when greedy = true
  bool matched = false;
  int matched_len = 0, matched_id = 0;

  while (s != end){
    UniChar letter = read_uni_char(&s, end);
    state.step(letter);
    if (not state.any()){
      // Break out of the loop since no more active states.
      break;
    }

    // Go through the active states and find if any are terminating. Match
    // the id with the highest id among the terminating states. This is
    // needed for the operation of the lexer. This means that the rule that
    // was added the latest will get precedence if it matches the same text
    // like an older rule.
    int max_id = -1;
    for (unsigned int i = 0; i < state.active_nodes.size; i++){
      NFANode* node = state.active_nodes[i];

      if (node->terminating()){
        NFATermNode* term_node = (NFATermNode*) node;
        int this_id = term_node->id;

        if (this_id > max_id){
          max_id = this_id;
          matched_len = s - start;
          matched_id = this_id;
          // Note the match and continue processing
          matched = true;
        }
      } // if node is terminating
    } // for node in active nodes

    if (matched and not greedy){
      *id = matched_id;
      *length = matched_len;
      return true;
    }
  } /* while (s != end) */

  if (matched){
    *id = matched_id;
    *length = matched_len;
    return true;
  }
  return false;
}

RESubExpression re_plus(RESubExpression expr)
{
  NFASplitNode* split_node = rnew NFASplitNode;
  split_node->children.append(expr.input);
  re_route(expr.output, split_node);

  RESubExpression result;
  result.input = expr.input;
  result.output = split_node;
  return result;
}

RESubExpression re_question(RESubExpression expr)
{
  NFASplitNode* split_node = rnew NFASplitNode;
  split_node->children.append(expr.input);
  split_node->extra = expr.output;

  RESubExpression result;
  result.input = split_node;
  result.output = split_node;
  return result;
}

void re_route(NFANode* output, NFANode* target)
{
  while (output != NULL) {
    output->route(target);
    output = output->extra;
  }; /* while output != NULL */
}

RESubExpression re_star(RESubExpression expr)
{
  NFASplitNode* split_node = rnew NFASplitNode;
  split_node->route(expr.input);
  re_route(expr.output, split_node);

  RESubExpression result;
  result.input = split_node;
  result.output = split_node;
  return result;
}

}
